package 二叉树;

import com.alibaba.fastjson.JSON;

import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class No113路径总和II {

    /**
     * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例:
     * 给定如下二叉树，以及目标和 sum = 22，
     *
     *               5
     *              / \
     *             4   8
     *            /   / \
     *           11  13  4
     *          /  \    / \
     *         7    2  5   1
     * 返回:
     *
     * [
     *    [5,4,11,2],
     *    [5,8,4,5]
     * ]
     */

    List<List<Integer>> resultList=new ArrayList<>();

    int sum;

    //效率不高,每次新建立List,需采用回溯,开始加入,随后吐出
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        this.sum=sum;
        dg(root,new ArrayList<>());
        return resultList;
    }

    private void dg(TreeNode node,List<Integer> list){
        if(node==null)
            return;
        list.add(node.val);
        if(node.left==null&&node.right==null){
            int sum = list.stream().mapToInt(Integer::intValue).sum();
            if(sum==this.sum)
                resultList.add(list);
        }
        /**
         * 无需新建立一个List,只需要在递归完后,将先前的吐出即可,这就叫回溯~
         */
        List<Integer> temp=new ArrayList<>(list);
        dg(node.left,list);
        dg(node.right,temp);
    }


    List<Integer> list=new ArrayList<>();

    public List<List<Integer>> pathSumGood(TreeNode root, int sum) {
        dg2(root,sum);
        return resultList;
    }

    /**
     * 回溯写法
     */
    private void dg2(TreeNode node,int number){
        if(node==null)
            return;
        list.add(node.val);
        number-=node.val;
        if(node.left==null&&node.right==null&&number==0) {
            resultList.add(new ArrayList<>(list));
        }
        dg2(node.left,number);
        dg2(node.right,number);
        list.remove(list.size()-1);
    }

    public static void main(String[] args) {
        TreeNode nodeByArr = TreeNode.getNodeByArr(new Integer[]{1, 2, null, 4});
        No113路径总和II n=new No113路径总和II();
        List<List<Integer>> lists = n.pathSumGood(nodeByArr, 7);
        System.out.println(JSON.toJSONString(lists));
    }

}
